/LMAR=0/XLINE=11/FONT#0=BASL30/FONT#1=BDR40/FONT#3=BASI30/FONT#4=BASB30/FONT#5=NGR25/FONT#6=NGR20/FONT#7=GRFX35/TMAR=30/PMAR=2130/BMAR=40



␈↓"∧␈↓ ↓H␈↓␈α?␈α?␈α?␈α?␈α?␈α?␈α?␈α'␈↓↓Introductory material␈↓
␈↓"!␈↓ ↓H␈↓Consider␈α
a␈αproblem␈α
which␈α
is␈αcast␈α
in␈αthe␈α
state-variable/operator␈α
formulation␈αdiscussed␈α
in␈α[Nilsson].␈α
The
␈↓ ↓H␈↓␈↓βgoal␈↓␈αis␈αsimply␈αone␈α(or␈αmore)␈αstates,␈αas␈αis␈αthe␈α␈↓βinitial␈αsituation␈↓.␈αFrom␈αany␈αgiven␈αstate␈αS,␈αseveral␈αoperators
␈↓ ↓H␈↓may␈α∞be␈α∞applicable.␈α∞Whichever␈α∞one␈α∞is␈α∞applied,␈α∞it␈α∞transforms␈α∞the␈α∞current␈α∞state␈α∞into␈α∞another␈α∞one.␈α
This
␈↓ ↓H␈↓paper␈α∞considers␈α
the␈α∞following␈α∞task:␈α
examine␈α∞the␈α∞original␈α
set␈α∞R␈α
of␈α∞operators,␈α∞and␈α
preprocess␈α∞it␈α∞into␈α
a
␈↓ ↓H␈↓new␈αset␈αD␈αof␈αdeterministic␈αoperators␈α(from␈αany␈αgiven␈αstate␈αat␈αmost␈αone␈αoperator␈αfrom␈αD␈αis␈αapplicable)
␈↓ ↓H␈↓yet␈αany␈αstate␈αwhich␈αcould␈αbecome␈αthe␈αgoal␈αstate␈αby␈αsome␈αsequence␈αof␈αoperators␈αin␈αR,␈αnow␈αbecomes␈αthe
␈↓ ↓H␈↓goal␈α∞state␈α
by␈α∞a␈α
sequence␈α∞of␈α
operators␈α∞from␈α
D.␈α∞ In␈α
other␈α∞words,␈α
we␈α∞still␈α
want␈α∞to␈α
be␈α∞able␈α
to␈α∞solve␈α
any
␈↓ ↓H␈↓solvable␈αnode,␈αyet␈αat␈α
each␈αnode␈αwe␈αwant␈α
there␈αto␈αbe␈αa␈αunique␈α
operator␈αwhich␈αis␈αapplicable.␈α
Thus␈αthe
␈↓ ↓H␈↓actual␈αsolution␈αprocess␈α
will␈αnot␈αinvolve␈α
searching.␈α Of␈αcourse␈α
searching␈αcannot␈αmagically␈αdisappear:␈α
the
␈↓ ↓H␈↓procedure which preprocesses R will have to involve either searching or unlimited parallel processing.
␈↓"!␈↓ ↓H␈↓Each␈α∃operator␈α∃consists␈α⊗of␈α∃a␈α∃predicate,␈α⊗whose␈α∃conjuncts␈α∃are␈α∃called␈α⊗preconditions,␈α∃and␈α∃a␈α⊗set␈α∃of
␈↓ ↓H␈↓assignments.␈α  <X␈α:␈α P(X)?␈α  T(X)>␈αis␈αan␈αabbreviated␈αway␈αof␈αspecifying␈αan␈αoperator␈αwhose␈αpredicate␈αP
␈↓ ↓H␈↓examines␈αvariables␈α
from␈αX={x␈↓#vi␈↓#}␈αand,␈α
if␈αit␈α
is␈αsatisfied,␈αcarries␈α
out␈αall␈αthe␈α
transformations␈α{x␈↓#vi␈↓#␈α
←␈αT(x␈↓#vi␈↓#)}.
␈↓ ↓H␈↓Let␈αINITIAL␈αbe␈αthe␈αinitial␈αstate,␈αA␈↓#vo␈↓#␈αthe␈αfinal␈αgoal␈αstate,␈αR␈αthe␈αset␈αof␈αoperators␈αwe␈αare␈αgiven,␈αD␈αthe␈αset
␈↓ ↓H␈↓of deterministic operators we must create.
␈↓"!␈↓ ↓H␈↓Our␈α∞procedure␈α∞is␈α∞not␈α∞very␈α∞complicated.␈α∞We␈α∞shall␈α∞create␈α∞several␈α∞alternate␈α∞sets␈α∞D␈↓#vj␈↓#.␈α∞ Whenever␈α∞one␈α∞of
␈↓ ↓H␈↓them␈αcontains␈αan␈αoperator␈αwhich␈αcan␈αbe␈αapplied␈αto␈αINITIAL,␈αwe␈αmay␈αstop␈αand␈αuse␈αthat␈αset␈αas␈αour␈αD.
␈↓ ↓H␈↓Our␈α
procedure␈α
will␈αguarantee␈α
that␈α
only␈α
one␈αoperator␈α
will␈α
apply␈α
to␈αeach␈α
succeeding␈α
state,␈α
until␈αfinally
␈↓ ↓H␈↓we arrive in state A␈↓#vo␈↓# and stay there.
␈↓"!␈↓ ↓H␈↓One␈α⊃operator␈α⊃which␈α⊃surely␈α⊂can␈α⊃go␈α⊃into␈α⊃D␈α⊂is␈α⊃the␈α⊃HALT␈α⊃operator,␈α⊂which␈α⊃we␈α⊃shall␈α⊃call␈α⊃d␈↓#vo␈↓#,␈α⊂whose
␈↓ ↓H␈↓preconditions␈α
are␈α
all␈α
of␈α
A␈↓#vo␈↓#,␈α
and␈α
which␈α
performs␈α
no␈α
transformations␈α
at␈α
all:␈α
 when␈α
we␈α
are␈α
in␈α∞the␈α
goal
␈↓ ↓H␈↓state,␈α
we␈α∞stay␈α
there.␈α∞ This␈α
gives␈α∞us␈α
an␈α∞initial␈α
set␈α∞D␈↓#vo␈↓#␈α
=␈α∞{d␈↓#vo␈↓#}.␈α
 If␈α∞INITIAL␈α
falls␈α∞within␈α
the␈α∞domain␈α
of
␈↓ ↓H␈↓applicability␈αof␈αone␈αof␈αthese␈αoperators,␈αwe␈αare␈αdone␈α(if␈αwe␈αstart␈αout␈αalready␈αin␈αthe␈αgoal␈αstate,␈αwe␈αnever
␈↓ ↓H␈↓leave it).
␈↓"!␈↓ ↓H␈↓To␈αconsider␈αless␈αtrivial␈αcases,␈αwe␈αcontinue␈αour␈αprocedure.␈α At␈αany␈αstage␈αwe␈αshall␈αhave␈αa␈αlarge␈α
collection
␈↓ ↓H␈↓␈↓↓C␈↓␈αof␈αpossible␈αsets␈α
D␈↓#vj␈↓#␈αof␈αoperators␈αd␈↓#vj␈↓#␈↓#vk␈↓#.␈α Pick␈α
any␈αsuch␈αD␈↓#vj␈↓#␈α(or,␈αalternately,␈α
work␈αon␈αthem␈αall␈αin␈α
parallel).
␈↓ ↓H␈↓Pick␈α
one␈α
of␈α
its␈α
operators␈αd␈↓#vj␈↓#␈↓#vk␈↓#.␈α
Now␈α
look␈α
at␈α
all␈αthe␈α
operators␈α
in␈α
R.␈α
Can␈αany␈α
of␈α
them␈α
ever␈α
help␈αto␈α
acheive
␈↓ ↓H␈↓the␈α
preconditions␈α
which␈α
d␈↓#vj␈↓#␈↓#vk␈↓#␈α∞demands␈α
in␈α
order␈α
to␈α
work?␈α∞ If␈α
so,␈α
what␈α
specializations,␈α∞what␈α
constraints
␈↓ ↓H␈↓can␈α∞be␈α∞put␈α∞upon␈α∞the␈α∞helping␈α∞operator?␈α∞ For␈α∞every␈α∞such␈α∞more␈α∞deterministic␈α∞operator␈α∞r,␈α∞add␈α∞it␈α∞to␈α∞D␈↓#vj␈↓#,
␈↓ ↓H␈↓making␈αa␈αnew,␈αseparate␈α possible␈αset␈αfor␈αD,␈αa␈αnew␈αelement␈αof␈α␈↓↓C␈↓.␈αThrow␈αit␈αaway␈αimmediately␈αif␈αit␈αis␈αno
␈↓ ↓H␈↓longer␈αdeterministic:␈αif␈αr␈αcan␈αbe␈αapplied␈αin␈αany␈αsituation␈αthat␈αany␈αother␈αoperator␈αin␈αD␈↓#vj␈↓#␈αcan␈αbe␈αapplied
␈↓ ↓H␈↓in.␈αNotice␈αthe␈αfantastic␈αrate␈αof␈αgrowth␈αof␈α␈↓↓C␈↓.␈α  If␈αwe␈αever␈αconsider␈αa␈αD␈↓#vj␈↓#␈αwhich␈αhas␈αno␈αoperators␈αwhich
␈↓ ↓H␈↓can␈α
be␈α
helped,␈α
and␈α
none␈α
which␈α
apply␈α
to␈α
INITIAL,␈α
then␈α
we␈α
may␈α
throw␈α
that␈α
D␈↓#vj␈↓#␈α
away␈α
also.␈α
 This␈α
process
␈↓ ↓H␈↓continues␈αuntil␈α
some␈αd␈↓#vi␈↓#␈↓#vj␈↓#␈α
in␈αsome␈α
D␈↓#vi␈↓#␈αcan␈αbe␈α
applied␈αto␈α
INITIAL.␈αWhen␈α
this␈αhappens,␈α
we␈αknow␈αthat␈α
d␈↓#vi␈↓#␈↓#vj␈↓#
␈↓ ↓H␈↓is␈α_just␈α_helping␈α_to␈α_establish␈α_the␈α_preconditions␈α_for␈α_another␈α_operator␈α_which␈α_will␈α_establish␈α↔the
␈↓ ↓H␈↓preconditions.... which will establish the preconditions for d␈↓#vo␈↓# which means that we are in state A␈↓#vo␈↓#.






␈↓"∧␈↓ ↓H␈↓␈↓εFebruary 6, 1975␈↓ Dpage 1



␈↓"∧␈↓ ↓H␈↓␈α?␈α?␈α?␈α?␈αβ␈↓↓An example: the Monkey and Bananas Problem␈↓
␈↓"!␈↓ ↓H␈↓To␈αillustrate␈αthe␈αbasic␈αidea,␈αwe␈αshall␈α
work␈αthrough␈αa␈αsimplified␈αversion␈αof␈αthe␈αinfamous␈α
Monkey␈αand
␈↓ ↓H␈↓Bananas Problem.
␈↓"!␈↓ ↓H␈↓A␈α
␈↓βstate␈↓␈α
S␈α
has␈α
only␈αtwo␈α
components,␈α
(m,b),␈α
indicating␈α
the␈α
position␈αof␈α
the␈α
monkey␈α
and␈α
the␈α
position␈αof␈α
the
␈↓ ↓H␈↓box.␈αThe␈αonly␈αdistinguished␈αpositions␈αare␈αBA␈α(the␈αposition␈αof␈αthe␈αbananas),␈αm␈↓#vi␈↓#␈α(the␈αinitial␈αposition␈αof
␈↓ ↓H␈↓the monkey), and b␈↓#vi␈↓# (the initial position of the box).
␈↓"!␈↓ ↓H␈↓There␈α∞are␈α∞only␈α∂two␈α∞operators,␈α∞Go␈α∂and␈α∞Push.␈α∞Go(x,y)␈α∞will␈α∂transport␈α∞the␈α∞monkey␈α∂from␈α∞ x␈α∞to␈α∂y.␈α∞More
␈↓ ↓H␈↓formally,␈α
Go(x,y)␈α
applies␈α
to␈α
a␈α
state␈α
whose␈αmonkey-position␈α
is␈α
x,␈α
and␈α
performs␈α
the␈α
assignment␈αx:=y.␈α
 The
␈↓ ↓H␈↓precondition␈αis␈αthat␈α the␈αmonkey␈αis␈αnot␈αalready␈αat␈α
y,␈αthat␈αis,␈αx␈↓π≠␈↓y.␈α Push(x,b,y)␈αlets␈αthe␈αmonkey␈αpush␈α
the
␈↓ ↓H␈↓box␈α
to␈α
y.␈α
 A␈α
state␈α
(x,b)␈α
is␈α
transformed␈α
into␈α(y,y).␈α
The␈α
precondition␈α
is␈α
that␈α
the␈α
monky␈α
be␈α
at␈α
the␈αbox,␈α
x=b,
␈↓ ↓H␈↓and that this position is different from y, x␈↓π≠␈↓y.
␈↓"!␈↓ ↓H␈↓With␈α∞this␈α∂statement␈α∞of␈α∞the␈α∂problem,␈α∞a␈α∂complete␈α∞graph␈α∞of␈α∂the␈α∞situation␈α∂can␈α∞be␈α∞grown,␈α∂but␈α∞it␈α∂will␈α∞of
␈↓ ↓H␈↓necessity be nondeterministic:
␈↓"	␈↓ ↓H␈↓π                        (mi,bi)

␈↓"	␈↓ ↓H␈↓π           go(mi,bi)               go(mi,y) with y≠bi



␈↓"	␈↓ ↓H␈↓π                          go(y,bi)
␈↓"	␈↓ ↓H␈↓π              (bi,bi) ================= (y,bi)         loop via go(y,y') with y'≠bi
␈↓"	␈↓ ↓H␈↓π                      go(bi,y) with y≠bi

␈↓"	␈↓ ↓H␈↓πpush(bi,bi,BA)           push(bi,bi,z) with z≠BA,z≠bi


␈↓"	␈↓ ↓H␈↓π        (BA,BA)←ααααααααα(z,z)
␈↓"	␈↓ ↓H␈↓π            push(bi,bi,BA)
␈↓"	␈↓ ↓H␈↓π                                    go(z)
␈↓"	␈↓ ↓H␈↓π                          go(y)
␈↓"	␈↓ ↓H␈↓π                                   (y,z)               loop via go(y,y') with y'≠z
␈↓"!␈↓ ↓H␈↓The␈α∞first␈α∞step␈α
in␈α∞ our␈α∞preprocessing␈α
is␈α∞to␈α∞admit␈α
the␈α∞HALT␈α∞operator,␈α
whose␈α∞precondition␈α∞is␈α∞the␈α
goal
␈↓ ↓H␈↓state, (BA,BA), and which makes no change in that state.  We shall also refer to this operator as d␈↓#vo␈↓#.


␈↓"	␈↓ ↓H␈↓π(BA,BA)           HALT


␈↓"!␈↓ ↓H␈↓The␈αnext␈αstep␈αis␈α
to␈αexamine␈αall␈αthe␈α operators␈α
in␈αR={go,␈αpush},␈αto␈αsee␈α
how␈αthey␈αmight␈αhelp␈αacheive␈α
the
␈↓ ↓H␈↓preconditions␈αof␈αsome␈αoperator␈αin␈αD␈↓#vo␈↓#={d␈↓#vo␈↓#}.␈α go(x,BA)␈αcan␈αbring␈αabout␈αthe␈αgoal,␈αprovided␈αthat␈αthe␈αbox

␈↓"∧␈↓ ↓H␈↓␈↓εFebruary 6, 1975␈↓ Dpage 2



␈↓"∧␈↓ ↓H␈↓is␈α
already␈α
at␈α
BA␈αbut␈α
that␈α
the␈α
monkey␈α
isn't.␈α Notice␈α
how␈α
crucial␈α
it␈αis␈α
that␈α
go(x,x)␈α
be␈α
illegal:␈αotherwise
␈↓ ↓H␈↓our␈α∀set␈α∪D␈α∀would␈α∪already␈α∀be␈α∀nondeterministic␈α∪(from␈α∀(BA,BA)␈α∪we␈α∀could␈α∪apply␈α∀both␈α∀HALT␈α∪and
␈↓ ↓H␈↓go(BA,BA)).  We thus have the following graph so far:


␈↓"	␈↓ ↓H␈↓π(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x≠BA
␈↓"	␈↓ ↓H␈↓π                go(x,BA)


␈↓"	␈↓ ↓H␈↓π      HALT
␈↓"!␈↓ ↓H␈↓The␈α
push␈α
operator␈α
can␈α∞acheive␈α
the␈α
preconditions␈α
of␈α∞HALT␈α
iff␈α
the␈α
current␈α∞state␈α
is␈α
of␈α
the␈α∞form␈α
(z,z),
␈↓ ↓H␈↓where␈αz␈↓π≠␈↓BA.␈αAgain,␈αthis␈αlast␈αcondition␈αis␈αcrucial␈αto␈αkeeping␈αD␈αdeterministic.␈αOur␈αnew␈αtentative␈αD␈αthus
␈↓ ↓H␈↓contains three operators now:
␈↓"	␈↓ ↓H␈↓d␈↓#vo␈↓# = HALT; precondition is (BA,BA), transformation is null.
␈↓"	␈↓ ↓H␈↓d␈↓#v1␈↓# = go(BA); precondition is (x␈↓π≠␈↓BA,BA), transformation is x:=BA.
␈↓"	␈↓ ↓H␈↓d␈↓#v2␈↓# = push(x,x,BA); precondition is (x␈↓π≠␈↓BA,x), transformation is x:=BA.

␈↓"	␈↓ ↓H␈↓π                        (x,x) with x≠BA


␈↓"	␈↓ ↓H␈↓π                    push(x,x,BA)


␈↓"	␈↓ ↓H␈↓π(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x≠BA
␈↓"	␈↓ ↓H␈↓π                go(x,BA)


␈↓"	␈↓ ↓H␈↓π      HALT
␈↓"!␈↓ ↓H␈↓There␈αis␈α
no␈αother␈α
way␈αthat␈αeither␈α
push␈αor␈α
go␈αcan␈αhelp␈α
acheive␈αthe␈α
preconditions␈αthat␈αHALT␈α
demands.
␈↓ ↓H␈↓We␈α
now␈α
turn␈α
to␈α
ways␈α
to␈α
help␈α
operators␈α
in␈α
D␈↓#v1␈↓#={d␈↓#vo␈↓#,d␈↓#v1␈↓#,d␈↓#v2␈↓#}.␈α
 Nothing␈α
can␈α
help␈α
d␈↓#vo␈↓#␈α
or␈α
d␈↓#v1␈↓#.␈α
For␈αd␈↓#v2␈↓#,␈α
however,
␈↓ ↓H␈↓we␈α∪find␈α∀that␈α∪go(z,x)␈α∪␈↓βcan␈↓␈α∀bring␈α∪about␈α∪(x,x),␈α∀but␈α∪only␈α∪when␈α∀the␈α∪box␈α∪was␈α∀originally␈α∪at␈α∀x.␈α∪ This
␈↓ ↓H␈↓unfortunately␈α∞conflicts␈α∂with␈α∞d␈↓#v1␈↓#,␈α∂in␈α∞the␈α∞situation␈α∂(x,BA).␈α∞So␈α∂we␈α∞stipulate␈α∞that␈α∂our␈α∞new␈α∂specialized␈α∞go
␈↓ ↓H␈↓operator␈αmust␈αonly␈αapply␈αwhen␈αthe␈αbox␈αis␈α␈↓βnot␈↓␈αat␈αBA.␈α A␈αsmart␈αalgorithm␈αwould␈αrecognize␈αthat␈αthe␈αtwo
␈↓ ↓H␈↓operators␈αd␈↓#v1␈↓#␈αand␈αour␈αnew␈αd␈↓#v3␈↓#␈αcan␈αbe␈αcombined,␈αsince␈αfrom␈α(x,BA)␈αwe␈αgo␈αto␈α(BA,BA),␈αwhile␈αfrom␈α(z,x)
␈↓ ↓H␈↓we␈α∩go␈α∩to␈α∩(x,x)␈α∩when␈α∩x␈↓π≠␈↓BA.␈α∩ These␈α∩both␈α∩could␈α∩become␈α∩a␈α∩single␈α∩go␈α∩operator,␈α∩go(z,x)␈α∩whose␈α∩only
␈↓ ↓H␈↓precondition␈α∂is␈α∂that␈α∂z␈α∂does␈α∂not␈α∂already␈α∂equal␈α∂x.␈α∂ The␈α∂algorithm␈α∂we␈α∂later␈α∂present␈α∂does␈α∂not␈α∂do␈α∂such
␈↓ ↓H␈↓optimizations, so our picture must remain cluttered:







␈↓"∧␈↓ ↓H␈↓␈↓εFebruary 6, 1975␈↓ Dpage 3




␈↓"	␈↓ ↓H␈↓π(z,x) with z≠x, x≠BA


␈↓"	␈↓ ↓H␈↓π                    go(z,x)


␈↓"	␈↓ ↓H␈↓π                        (x,x) with x≠BA


␈↓"	␈↓ ↓H␈↓π                    push(x,x,BA)


␈↓"	␈↓ ↓H␈↓π(BA,BA) ←ααααααααααααααααααααααααα(x,BA) with x≠BA
␈↓"	␈↓ ↓H␈↓π                go(x,BA)


␈↓"	␈↓ ↓H␈↓π      HALT
␈↓"!␈↓ ↓H␈↓We␈α∀finally␈α∀arrive␈α∀at␈α∀a␈α∀set␈α∀D␈↓#v2␈↓#={d␈↓#vo␈↓#,d␈↓#v1␈↓#,d␈↓#v2␈↓#,d␈↓#v3␈↓#}␈α∀which␈α∀contains␈α∀operators␈α∀which␈α∀can␈α∀apply␈α∀in␈α∀any
␈↓ ↓H␈↓conceivable␈αstate␈αof␈αthe␈αworld,␈αyet␈αno␈αtwo␈αof␈αwhich␈αever␈αwant␈αto␈αapply␈αto␈αthe␈αsame␈αsame.␈α Incidentally,
␈↓ ↓H␈↓there␈α
is␈α
no␈α
way␈α
either␈α
operator␈α
in␈α
R␈αcan␈α
be␈α
further␈α
specialized␈α
to␈α
help␈α
acheive␈α
the␈α
preconditions␈αof␈α
any
␈↓ ↓H␈↓operator␈αin␈αD␈↓#v2␈↓#.␈α Thus␈αour␈αprocedure␈αterminates␈αhere␈αfor␈αtwo␈αreasons␈α(success␈αand␈αexhaustion).␈α Notice
␈↓ ↓H␈↓how␈αmuch␈αmore␈αdirect␈αthe␈αabove␈αgraph␈αis;␈αnot␈αonly␈αis␈αevery␈αoriginal␈αinitial␈αstate␈αstill␈αsolvable,␈αbut␈αthe
␈↓ ↓H␈↓solution path is in no case any longer than the ideal path using operators from R.





















␈↓"∧␈↓ ↓H␈↓␈↓εFebruary 6, 1975␈↓ Dpage 4